#include <iostream>
using namespace  std;
typedef  struct  Node
{
    int data;
    struct  Node*  next;

}Node;
void SelectSort(Node* head)
{
    //h永远指向当前链表无序区的第一个位置
    Node* h=head->next;
    head->next= nullptr;
    Node* rear= head;
    Node* premin= nullptr;   //指向值最小的结点的前驱结点
    Node* min= nullptr;  //指向值最小的结点

    //只要无序区仍然有元素 就把无序区中的最小的元素加入到有序区
    while(h)
    {
        premin= nullptr;
        min=h;
        Node* pre= h;
        Node* p=h->next;//从h出发
        while(p)
        {
            if(p->data<min->data)
            {
                premin=pre;
                min=p;
            }
            p=p->next;
            pre=pre->next;
        }
        //只要min发生 premin一定不为空
        if(premin== nullptr)//首元结点是最小结点
        {
             rear->next=min;
             rear=min;
             h=h->next;
        } else{
            //最小的不是首元结点
            rear->next=min;
            rear=min;
            //删除该结点
            premin->next=min->next;
        }
        //将最小结点尾插之后修改后继指针为空
        rear->next= nullptr;
        //无序区的第一个结点发生改变

    }
}
void print(Node* head)
{
    Node* p=head->next;
    while (p)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}
int main() {

    Node* head =new Node;
    head->next= nullptr;
    Node* rear=head;
    int n;
    cin>>n;
    //初始化链表
    while(n--) {
        int num;
        cin >> num;
        Node *temp = new Node;
        temp->data = num;
        temp->next = nullptr;
        rear->next = temp;
        rear=temp;
    }
    print(head);
    SelectSort(head);
    print(head);





    return 0;
}
